package main.剑指OfferⅡ;

import java.util.*;

public class Day1_Day4 {
    public static void main(String[] args) {
        System.out.println("**************************Day1**************************");
        System.out.println("剑指OfferⅡ001.整数除法");
        System.out.println("剑指OfferⅡ002.二进制加法");
        System.out.println("剑指OfferⅡ003.前n个数字二进制中1的个数");
        System.out.println("**************************Day2**************************");
        System.out.println("剑指OfferⅡ004.只出现一次的数字");
        System.out.println("剑指OfferⅡ005.单词长度的最大乘积");
        System.out.println("剑指OfferⅡ006.排序数组中两个数字之和");
        System.out.println("**************************Day3**************************");
        System.out.println("剑指OfferⅡ007.数组中和为0的三个数");
        System.out.println("剑指OfferⅡ008.和大于等于target的最短子数组");
        System.out.println("剑指OfferⅡ009.乘积小于K的子数组");
        System.out.println("**************************Day4**************************");
        System.out.println("剑指OfferⅡ010.和为k的子数组");
        System.out.println("剑指OfferⅡ011.0和1个数相同的子数组");
        System.out.println("剑指OfferⅡ012.左右两边子数组的和相等");
        System.out.println("剑指OfferⅡ013.二维子矩阵的和");
    }
}

class Offer001{
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        // 环境只支持存储 32 位整数
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int res = 0;
        while (a <= b) {
            a -= b;
            res++;
        }
        return sign == 1 ? res : -res;
    }
}

class Offer002{
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }
}

class Offer003{
    public int[] countBits(int n) {
        int[] result=new int[n+1];
        for (int i=0;i<=n;i++){
            result[i]=Integer.bitCount(i);
        }
        return result;
    }
}

class Offer004{
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int result=0,i=0;
        while (i<nums.length){
            if (i+2<nums.length&&nums[i]==nums[i+2]){
                i+=3;
            }else {
                result=nums[i];
                break;
            }
        }
        return result;
    }
}

class Offer005{
    public boolean process(Set<Character> s1,Set<Character> s2){
        for (char c: s1){
            if (s2.contains(c)) return false;//包含相同
        }
        return true;
    }
    public int maxProduct(String[] words) {
        int max=0;
        List<Set<Character>> setList=new ArrayList<>();
        for (String word:words){
            char[] str=word.toCharArray();
            Set<Character> set=new HashSet<>();
            for (char c:str){
                if (!set.contains(c)) set.add(c);
            }
            setList.add(set);
        }
        for (int i=0;i< words.length;i++){
            for (int j=i+1;j< words.length;j++){
                if (process(setList.get(i),setList.get(j))){
                    max=Math.max(words[i].length()*words[j].length(),max);
                }
            }
        }
        return max;
    }
}

class Offer006{
    public int[] twoSum(int[] numbers, int target) {
        int[] result=new int[2];
        int left=0,right= numbers.length-1;
        while (left<right){
            if (numbers[left]+numbers[right]>target) right--;
            else if (numbers[left]+numbers[right]<target) left++;
            else {
                result[0]=left;
                result[1]=right;
                break;
            }
        }
        return result;
    }
}

class Offer007{
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);
        for (int i=0;i< nums.length;i++){
            if (nums[i]>0) return result;//大于0，后续不存在
            if (i>0&&nums[i]==nums[i-1]) continue;//去重
            int left=i+1,right= nums.length-1;//双指针
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if (sum>0) right--;
                else if (sum<0) left++;
                else {
                    List<Integer> curList=new ArrayList<>();
                    curList.add(nums[i]);
                    curList.add(nums[left]);
                    curList.add(nums[right]);
                    result.add(curList);
                    while (right>left&&nums[right]==nums[right-1]) right--;//去重
                    while (right>left&&nums[left]==nums[left+1]) left++;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

class Offer008{
    public int minSubArrayLen(int target, int[] nums) {
        int left=0,right=-1,min=Integer.MAX_VALUE,sum=0;
        while (right< nums.length){//窗口右扩
            if (sum<target){
                right++;
                if (right< nums.length)  sum+=nums[right];
            }else {//窗口左缩
                min=Math.min(min,right-left+1);
                sum-=nums[left];
                left++;
            }
        }
        return min==Integer.MAX_VALUE ? 0 : min;
    }
}

class Offer009{
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int length=nums.length,count=0;
        for (int i=0;i<length;i++){
            int mul=1;
            for (int j=i;j<length;j++){
                mul*=nums[j];
                if (mul<k) count++;
                else break;
            }
        }
        return count;
    }
}

class Offer010{
    public int subarraySum(int[] nums, int k) {
        int count=0,sum=0;
        int[] dp=new int[nums.length];
        for (int i=0;i< nums.length;i++){
            sum+=nums[i];
            dp[i]=sum;
        }
        for (int i=0;i< nums.length;i++){
            if (dp[i]==k) count++;
            for (int j=0;j<i;j++){
                if (dp[i]-dp[j]==k) count++;
            }
        }
        return count;
    }
}

class Offer011{
    public int findMaxLength(int[] nums) {
        int max=0,length= nums.length;
        int[] dp=new int[length];
        for (int i=0;i<length;i++){
            for (int j=i;j<length;j++){
                if (i==j) dp[j]=nums[j]==1 ? 1 : -1;
                else dp[j]=dp[j-1]+(nums[j]==1 ? 1 : -1);
                if (dp[j]==0) max=Math.max(max,j-i+1);
            }
        }
        return max;
    }
}

class Offer012{
    public int pivotIndex(int[] nums) {
        int[] preSum=new int[nums.length],lastSum=new int[preSum.length];
        int pre=0,last=0,result=-1;
        for (int i=0;i< nums.length;i++){
            last+=nums[nums.length-1-i];
            pre+=nums[i];
            preSum[i]=pre;
            lastSum[nums.length-1-i]=last;
        }
        for (int i=0;i< nums.length;i++){
            if (i==0) {
                if (lastSum[i+1]==0){
                    result=i;
                    break;
                }
            }else if (i== nums.length-1){
                if (preSum[i-1]==0){
                    result=i;
                    break;
                }
            }else if (preSum[i-1]==lastSum[i+1]){
                result=i;
                break;
            }
        }
        return result;
    }
}

class Offer013{
    int[][] nums;
    public Offer013(int[][] matrix) {
        nums=matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum=0;
        for (int i=row1;i<=row2;i++){
            for (int j=col1;j<=col2;j++){
                sum+=nums[i][j];
            }
        }
        return sum;
    }
}